1. Field of the Invention
The present invention relates to a programming method for concurrent programs and a supporting apparatus for parallelization.
2. Description of the Related Art
Along with the recent progress in semiconductor integrated circuit technology, complex processors or large-capacity memories with a small size can be realized at a low cost, resulting in actual use of concurrent processing systems or distributed processing systems consisting of a large number of processors. Such hardware requires a dedicated program, i.e., a concurrent program or a distributed processing program (to be referred to as a xe2x80x9cconcurrent programxe2x80x9d hereinafter). Therefore, efficient development of a concurrent program is an important factor as in examination of an excellent algorithm.
In program development, a step of finding and correcting a bug in a program (i.e., debug) largely influences the efficiency of program development. In development of a concurrent program, however, a problem inherent to a concurrent program, which is unfamiliar in development of a sequential program, must be taken into consideration. Such a problem inherent to a concurrent program is that processes constituting a concurrent program may exhibit various behaviors depending on timings of interaction among processes, so the entire concurrent program does not properly operate. This problem based on the nature of the concurrent program is generally called xe2x80x9cnondeterminismxe2x80x9d.
Consider a concurrent program shown in FIGS. 1A and 1B.
Referring to FIG. 1A, a process P1 performs initialization (init) of a shared memory M, a process P2 performs read access (read) to the shared memory M, and a process P3 performs write access (write) to the shared memory M. When these processes are operated in concurrent processing system which executes these processes by different processors, a total of six (FIG. 1B) combinations of operations are available. Normally, the system starts processing with initialization. Assume that a correct result is obtained when the program is operated in an order of processes P1 (init)xe2x86x92P2 (read)xe2x86x92P3 (write) or P1 (init)xe2x86x92P3 (write)xe2x86x92P2 (read). In this case, as for the four remaining combinations (e.g., P2 (read)xe2x86x92P3 (write)xe2x86x92P1 (init)), since initialization is not performed first, a correct result cannot be obtained.
Whenever the concurrent program is operated, the above nondeterminism associated with the behaviors of processes change the result depending on the system status at that point of time. Therefore, unless the problem of nondeterminism is solved, the normal operation of the concurrent program cannot always be guaranteed although the concurrent program normally operates in a test mode.
In addition, it is difficult to detect a bug associated with nondeterminism as compared to a bug in a sequential program. In a sequential program, an operation can be confirmed by executing all paths in the program during a testing and debugging operation. To the contrary, in a concurrent program, paths must be executed in consideration of all matched paths (i.e., not only all paths in each process but also behaviors among processes). When the number of processes is small, as in the above example, all behaviors among the processes can be relatively easily listed. In actual program development, however, the number of processes becomes large to result in a large number of combinations thereof. For this reason, it is impossible to cover all behaviors.
As described above, debugging in concurrent program development is much more difficult than that in sequential program development. Especially, a program itself recently becomes very large to make debugging more difficult.
It is an object of the present invention to provide a method of programming a concurrent program and a supporting apparatus for a parallelization, in which the concurrent program can be easily debugged and efficiently developed.
It is a gist of the present invention to temporarily convert a concurrent program into a sequential program, perform test and debugging operations for the sequential program, and restore the concurrency of the program upon completion of the testing and debugging operation. The original concurrent program is debugged as needed.
The reason why programming of a concurrent program is difficult is that xe2x80x9csince a human thinking is substantially sequential, it is difficult to logically recognize concurrently operated objects as they arexe2x80x9d. In the present invention, a concurrent program is temporarily converted into a sequential program, and programming or debugging (xe2x80x9cdebuggingxe2x80x9d used here means an operation including a test operation) is performed for the sequential program. The level of difficulty is the same as that of the conventional serialization. Upon completion of debugging, concurrency is automatically restored using the debugging information.
The above programming style is called xe2x80x9chyper serializationxe2x80x9d. According to this xe2x80x9chyper serializationxe2x80x9d, difficulty in programming by the conventional method can be solved. The basic concept of the present invention comprises the following three steps (or means).
(1) The step (means) of performing serialization of a concurrent program to generate a hyper sequential program.
(2) The step (means) of performing operations (programming, debugging, and introduction of concurrency) for the hyper sequential program.
(3) The step (means) of performing parallelization of the hyper sequential program upon completion of the operations to generate a concurrent program.
The xe2x80x9chyper sequential programxe2x80x9d here means a program which is serialized while information associated with the concurrent structure of an original concurrent program is maintained.
The parallelization for supporting apparatus is characterized by comprising: serialization means for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed; debugging means for debugging the sequential program and forming debugging information; and parallelization means for performing parallelization of the debugged sequential program on the basis of the debugging information to convert the sequential program into a second concurrent program. The method of programming a concurrent program, is characterized by comprising: the first step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed; the second step of debugging the sequential program and forming debugging information; and the third step of performing parallelization of the debugged sequential program on the basis of the debugging information to convert the sequential program into a second concurrent program.
Preferable embodiments of the present invention will be listed below.
(1) Information associated with concurrency is introduced into the hyper sequential program. The information associated with the concurrency includes, e.g., information associated with intended nondeterminism (to be described later).
(2) The concurrent structure of the first concurrent program is analyzed, and parallelization of the sequential program is performed by using concurrent structure and an execution result obtained upon testing of the sequential program.
(3) The concurrent structure of a section of the first concurrent program, which section is to be converted into the sequential program, and the sequential structure of a section of the sequential program are analyzed, and a correlation associated with the concurrent structure of the first concurrent program and a correlation associated with the sequential structure of the sequential program are displayed as graph information. In display of the graph information, the graph information is displayed while defining the predetermined section as a node, the correlation associated with the concurrent structure as the first arc, and the correlation associated with the sequential structure as the second arc. Concurrent programming of a selected section of the sequential program is performed to convert the section into a partial sequential program partially having the sequential structure. Concurrent programming of the partial sequential program is performed to convert the partial sequential program into a second concurrent program.
The step of converting the first concurrent program into the sequential program may include the step of debugging the sequential program until a desired execution result of the sequential program is obtained, or the step of converting the sequential program into the partial sequential program may include the step of debugging the partial sequential program until a desired execution result is obtained. Alternatively, both the steps may include the steps of performing testing and debugging operations.
The step of converting the sequential program into the partial sequential program may include the step of analyzing the sequential structure of the partial sequential program, and at the same time, steps of displaying the graph information, selecting the section to be converted into a concurrent program, and converting the section into the partial sequential program may be repeated a predetermined number of times.
(4) In serialization for converting the first concurrent program into a sequential program, the first concurrent program is executed, and an execute log in this step is stored. The stored execute log and the first concurrent program are analyzed, and the stored execute log is rearranged on the basis of an analysis result. In analysis of the execute log and the first concurrent program, a preceding relationship between processes is extracted from the stored execute log and the first concurrent program, and the preceding relationship is stored as preceding relationship information.
(5) In introduction of information associated with concurrency, the flow of processes of the sequential program is converted into a field consisting of a constraint and a transition condition, and this field is tuned. In addition, field data representing the field is displayed.
(6) A process group as a parallelization candidate for the sequential program is designated. The execution order of the process group is exchanged to convert the sequential program into a plurality of pseudo-concurrent programs. Thereafter, the plurality of pseudo-concurrent programs are converted into a partial sequential program partially having a sequential structure, and parallelization of the partial sequential program is performed to convert the partial sequential program into the second concurrent program.
The step of converting the first concurrent program into the sequential program may include the step of debugging the sequential program until a desired execution result of the sequential program is obtained, or the step of converting the plurality of pseudo-concurrent programs into a partial sequential program may include the step of debugging the plurality of pseudo-concurrent programs until a desired execution result of the pseudo-concurrent program group is obtained. Alternatively, both the steps may include the steps of performing testing and debugging operations. In designation of the process group as a parallelization candidate for the sequential program, the first concurrent program may be analyzed, and the process group as a candidate of parallelization may be extracted from an analysis result. The step of converting the sequential program into the plurality of pseudo-concurrent programs may include the step of eliminating a pseudo-concurrent program determined as unnecessary from an execution result of some of the plurality of pseudo-concurrent programs. The step of converting the plurality of pseudo-concurrent programs into a partial sequential program may include the step of designating the process group as a parallelization candidate for the partial sequential program, and the step of converting the sequential program into the plurality of pseudo-concurrent programs and the step of converting the plurality of pseudo-concurrent programs into a partial sequential program may be repeated a predetermined number of times.
(7) When the first concurrent program is to be converted into the sequential program in accordance with a predetermined serializing rule, information associated with concurrency is introduced to the sequential program by correcting the serializing rule.
(8) In an apparatus for supporting concurrent programming, which supports programming of a concurrent program used in an execution environment in which a process group operates in a concurrent manner while exchanging message information, log information corresponding to the execution history of the process group of the concurrent program is acquired and stored as a serializing rule, and the stored log information can be corrected. The process group can be sequentially started and controlled on the basis of the stored log information, and parallelization of the stored log information is performed to convert the log information into a second concurrent program.
The log information correcting means includes display means for time-serially displaying the log information stored in the log information storing means, rearrangement designating means for designating rearrangement of an order of data in the log information time-serially displayed by the display means, and rewrite means for rewriting the log information stored in the log information storing means in accordance with a designation from the rearrangement designating means. The log information correcting means includes nondeterminism introduction means for introducing nondeterminism of a processing timing between processes.
(9) In a system in which a process group operates in accordance with execution order definition information in an execution environment in which the process group can operate in a concurrent manner while exchanging message information, the execution order definition information is divided, and the process group is started and controlled on the basis of the divided execution order information.
In this case, the means for holding the division criterion designating means for supplying a criterion for dividing the execution order definition information may also be provided. The history of message exchange is used as the execution order definition information, and at the same time, destination process information in the message is used as a division criterion in the division criterion designating means. The history of message exchange is used as the execution order definition information, the destination process information in the message is used as a division criterion in the division criterion designating means, and at the same time, the means for holding the process control means in units of processes is also provided. The history of message exchange is used as the execution order definition information, the destination process information in the message is used as a division criterion in the division criterion designating means, and at the same time, the means for holding the process control means in units of processes, and the division execution order information storing means for independently storing the execution order information divided by the execution order information division means are also provided. The process control means starts and controls the process on the basis of the division execution order information stored in the division execution order storing means corresponding to the process. Log information corresponding to the execution history information of the process group may be used as the execution order definition information.
(10) A test of the first concurrent program having a concurrent structure is executed. An execute log determined to have no bug upon execution of the test is accumulated, and parallelization of only the accumulated execute logs having no bug is performed to convert the execute logs into the second concurrent program. In addition, an execute log determined to have a bug upon execution of the test is accumulated, and the first concurrent program is corrected on the basis of the accumulated execute logs having bugs.
In the present invention, a concurrent program is temporarily serialized, and the sequential program is tested/debugged. With this operation, the concurrent program can be debugged at the same level of difficulty as that of serialization which is much easier than the conventional parallelization.
The concurrent information and the serialization information are simultaneously presented to the user by the graph information. With this operation, the user can designate a intended nondeterministic portion while considering the concurrent structure of the first concurrent program. In addition, the intended nondeterministic portion is designated/canceled not at the concurrent program description level but for the graph information. For this reason, a concurrent program can be easily developed without requiring an advanced parallelization technique.
In conversion of the first concurrent program into the sequential program, the first concurrent program and the execute log thereof are analyzed, and the execute log is rearranged on the basis of the analysis result. With this operation, the rearranged execute log is displayed and presented to the user, thereby facilitating understanding of the process of execution of the concurrent program and improving the efficiency of the debugging operation.
In introduction of the information associated with concurrency to the sequential program, the flow of the processes of the sequential program is converted into a field consisting of a constraint and a transition condition, and field data is displayed. The field is interrogatively and visually edited to effectively introduce the information associated with the concurrency, thereby efficiently programming a concurrent program without any bug.
A process group as a parallelization candidate is designated for the sequential program serialized from the first concurrent program, and the execution order of the process group is exchanged to convert the sequential program into a plurality of pseudo-concurrent programs. Thereafter, the plurality of pseudo-concurrent programs are converted into a partial sequential program partially having a sequential structure, and parallelization of the partial sequential program is performed to convert the partial sequential program into the second concurrent program. With this operation, the operation of the concurrent program can be sufficiently confirmed on the partial sequential program. In addition, when a process group as a parallelization candidate is designated for the partial sequential program, the sequential structured program can be gradually converted into a concurrent program. Furthermore, by introducing an information relating to concurrency which allows only nondeterminism confirmed to be properly operated in sequential execution based on a pseudo-concurrent behavior, a concurrent program which properly operates can be obtained. With this operation, the testing and debugging operation of a concurrent program is facilitated.
In an apparatus for supporting parallelization, which supports programming of a concurrent program used in an execution environment in which a process group of first concurrent program operates in a concurrent manner while exchanging message information, log information corresponding to the execution history of the process group is acquired and stored as a serializing rule. This log information can be corrected, and at the same time, the process group is sequentially started and controlled on the basis of the stored log information, thereby performing parallelization of the stored log information to convert the log information into the second concurrent program. In this case, the log information can be corrected without correcting the concurrent program as a source program to solve a drawback caused by nondeterminism of a processing timing. With this operation, the development of a concurrent/parallel/distributed program can be facilitated. In addition, since intended nondeterminism intended by the user can be easily introduced, flexibility, reutilization, and expansibility of a concurrent program can be maintained.
In a system in which a process group operates in accordance with execution order definition information in an execution environment in which the process group can operate in a concurrent manner while exchanging message information, the execution order definition information is divided, i.e., integrated log information of all processes, which is obtained by sequencing a concurrent program, is divided in units of processes, and the process group is started and controlled on the basis of the divided execution order information. With this operation, harmless nondeterminism is naturally introduced, and the same result as in execution of a sequential program on the basis of the integrated log information can be obtained at a higher processing efficiency.
The first concurrent program is tested, and an execute log determined to have no bug, which is one of thereof, upon execution of the test is accumulated. Concurrent programming of only the accumulated execute logs having no bug is performed to convert the execute logs into the second concurrent program. With this operation, the program can operate to allow only timing passing in the test, thereby preventing a bug which remains because of no execution of the test and improving the reliability.
Additional objects and advantages of the present invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the present invention. The objects and advantages of the present invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.